home *** CD-ROM | disk | FTP | other *** search
/ Enter 2006 September / Enter 09 2006.iso / Internet / SpamExperts Home 1.1 / SpamExperts Home.exe / lib / spamexperts.modules / spambayes / cdb.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2006-07-14  |  6.6 KB  |  240 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.4)
  3.  
  4. """
  5. Dan Bernstein's CDB implemented in Python
  6.  
  7. see http://cr.yp.to/cdb.html
  8.  
  9. """
  10. from __future__ import generators
  11. import os
  12. import struct
  13. import mmap
  14.  
  15. def uint32_unpack(buf):
  16.     return struct.unpack('<L', buf)[0]
  17.  
  18.  
  19. def uint32_pack(n):
  20.     return struct.pack('<L', n)
  21.  
  22. CDB_HASHSTART = 5381
  23.  
  24. def cdb_hash(buf):
  25.     h = CDB_HASHSTART
  26.     for c in buf:
  27.         h = h + (h << 5) & 0xFFFFFFFFL
  28.         h ^= ord(c)
  29.     
  30.     return h
  31.  
  32.  
  33. class Cdb(object):
  34.     
  35.     def __init__(self, fp):
  36.         self.fp = fp
  37.         fd = fp.fileno()
  38.         self.size = os.fstat(fd).st_size
  39.         self.map = mmap.mmap(fd, self.size, access = mmap.ACCESS_READ)
  40.         self.eod = uint32_unpack(self.map[:4])
  41.         self.findstart()
  42.         self.loop = 0
  43.         self.khash = 0
  44.         self.hpos = 0
  45.         self.hslots = 0
  46.         self.dpos = 0
  47.         self.dlen = 0
  48.  
  49.     
  50.     def close(self):
  51.         self.map.close()
  52.  
  53.     
  54.     def __iter__(self, fn = None):
  55.         len = 2048
  56.         while len < self.eod:
  57.             (klen, vlen) = struct.unpack('<LL', self.map[len:len + 8])
  58.             len += 8
  59.             key = self.map[len:len + klen]
  60.             len += klen
  61.             val = self.map[len:len + vlen]
  62.             len += vlen
  63.             if fn:
  64.                 yield fn(key, val)
  65.                 continue
  66.             yield (key, val)
  67.  
  68.     
  69.     def iteritems(self):
  70.         return self.__iter__()
  71.  
  72.     
  73.     def iterkeys(self):
  74.         return self.__iter__((lambda k, v: k))
  75.  
  76.     
  77.     def itervalues(self):
  78.         return self.__iter__((lambda k, v: v))
  79.  
  80.     
  81.     def items(self):
  82.         ret = []
  83.         for i in self.iteritems():
  84.             ret.append(i)
  85.         
  86.         return ret
  87.  
  88.     
  89.     def keys(self):
  90.         ret = []
  91.         for i in self.iterkeys():
  92.             ret.append(i)
  93.         
  94.         return ret
  95.  
  96.     
  97.     def values(self):
  98.         ret = []
  99.         for i in self.itervalues():
  100.             ret.append(i)
  101.         
  102.         return ret
  103.  
  104.     
  105.     def findstart(self):
  106.         self.loop = 0
  107.  
  108.     
  109.     def read(self, n, pos):
  110.         return self.map[pos:pos + n]
  111.  
  112.     
  113.     def match(self, key, pos):
  114.         if key == self.read(len(key), pos):
  115.             return 1
  116.         else:
  117.             return 0
  118.  
  119.     
  120.     def findnext(self, key):
  121.         if not self.loop:
  122.             u = cdb_hash(key)
  123.             buf = self.read(8, u << 3 & 2047)
  124.             self.hslots = uint32_unpack(buf[4:])
  125.             if not self.hslots:
  126.                 raise KeyError
  127.             
  128.             self.hpos = uint32_unpack(buf[:4])
  129.             self.khash = u
  130.             u >>= 8
  131.             u %= self.hslots
  132.             u <<= 3
  133.             self.kpos = self.hpos + u
  134.         
  135.         while self.loop < self.hslots:
  136.             buf = self.read(8, self.kpos)
  137.             pos = uint32_unpack(buf[4:])
  138.             if not pos:
  139.                 raise KeyError
  140.             
  141.             self.loop += 1
  142.             self.kpos += 8
  143.             u = uint32_unpack(buf[:4])
  144.             if u == self.khash:
  145.                 buf = self.read(8, pos)
  146.                 u = uint32_unpack(buf[:4])
  147.                 if u == len(key):
  148.                     if self.match(key, pos + 8):
  149.                         dlen = uint32_unpack(buf[4:])
  150.                         dpos = pos + 8 + len(key)
  151.                         return self.read(dlen, dpos)
  152.                     
  153.                 
  154.             u == len(key)
  155.             continue
  156.             None if self.kpos == self.hpos + (self.hslots << 3) else self
  157.         raise KeyError
  158.  
  159.     
  160.     def __getitem__(self, key):
  161.         self.findstart()
  162.         return self.findnext(key)
  163.  
  164.     
  165.     def get(self, key, default = None):
  166.         self.findstart()
  167.         
  168.         try:
  169.             return self.findnext(key)
  170.         except KeyError:
  171.             return default
  172.  
  173.  
  174.  
  175.  
  176. def cdb_dump(infile):
  177.     """dump a database in djb's cdbdump format"""
  178.     db = Cdb(infile)
  179.     for key, value in db.iteritems():
  180.         print '+%d,%d:%s->%s' % (len(key), len(value), key, value)
  181.     
  182.     print 
  183.  
  184.  
  185. def cdb_make(outfile, items):
  186.     pos = 2048
  187.     tables = { }
  188.     outfile.seek(pos)
  189.     for key, value in items:
  190.         outfile.write(uint32_pack(len(key)) + uint32_pack(len(value)))
  191.         h = cdb_hash(key)
  192.         outfile.write(key)
  193.         outfile.write(value)
  194.         tables.setdefault(h & 255, []).append((h, pos))
  195.         pos += 8 + len(key) + len(value)
  196.     
  197.     final = ''
  198.     for i in range(256):
  199.         entries = tables.get(i, [])
  200.         nslots = 2 * len(entries)
  201.         final += uint32_pack(pos) + uint32_pack(nslots)
  202.         null = (0, 0)
  203.         table = [
  204.             null] * nslots
  205.         for h, p in entries:
  206.             n = (h >> 8) % nslots
  207.             while table[n] is not null:
  208.                 n = (n + 1) % nslots
  209.             table[n] = (h, p)
  210.         
  211.         for h, p in table:
  212.             outfile.write(uint32_pack(h) + uint32_pack(p))
  213.             pos += 8
  214.         
  215.     
  216.     outfile.flush()
  217.     outfile.seek(0)
  218.     outfile.write(final)
  219.  
  220.  
  221. def test():
  222.     db = open('test.cdb', 'wb')
  223.     cdb_make(db, [
  224.         ('one', 'Hello'),
  225.         ('two', 'Goodbye'),
  226.         ('foo', 'Bar'),
  227.         ('us', 'United States')])
  228.     db.close()
  229.     db = Cdb(open('test.cdb', 'rb'))
  230.     print db['one']
  231.     print db['two']
  232.     print db['foo']
  233.     print db['us']
  234.     print db.get('ec')
  235.     print db.get('notthere')
  236.  
  237. if __name__ == '__main__':
  238.     test()
  239.  
  240.